package com.example.mergesort;

import com.example.algorithm.insertionsort.InsertionSort;

import java.util.Arrays;

public class MergeSort {

    public static <E extends Comparable<E>> void sort(E[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    private static <E extends Comparable<E>> void sort(E[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = l + (r - l) / 2;
        sort(arr, l, mid);
        sort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }

    public static <E extends Comparable<E>> void sort2(E[] arr, boolean useInsertionSort) {
        if (useInsertionSort) {
            sort3(arr, 0, arr.length - 1);
        } else {
            sort2(arr, 0, arr.length - 1);
        }
    }

    private static <E extends Comparable<E>> void sort2(E[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = l + (r - l) / 2;
        sort2(arr, l, mid);
        sort2(arr, mid + 1, r);
        // 优化点： if判断，如果前一个区间的最后一个元素比后一个区间的第一个元素小，就可以跳过merge了
        if (arr[mid].compareTo(arr[mid + 1]) > 0) {
            merge(arr, l, mid, r);
        }
    }

    private static <E extends Comparable<E>> void sort3(E[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        // 如果待排序的规模小于16时，使用插入排序来进行排序效率会更高，应为归并排序的常数更大
        if (r - l < 16) {
            InsertionSort.sort(arr, l, r);
            return;
        }
        int mid = l + (r - l) / 2;
        sort2(arr, l, mid);
        sort2(arr, mid + 1, r);
        // 优化点： if判断，如果前一个区间的最后一个元素比后一个区间的第一个元素小，就可以跳过merge了
        if (arr[mid].compareTo(arr[mid + 1]) > 0) {
            merge(arr, l, mid, r);
        }
    }

    private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r) {
        E[] tmpArr = Arrays.copyOfRange(arr, l, r + 1);
        int k = l;
        for (int i = l, j = mid + 1; i <= mid || j <= r; ) {
            if (i > mid) {
                arr[k++] = tmpArr[j++ - l];
            } else if (j > r) {
                arr[k++] = tmpArr[i++ - l];
            } else if (tmpArr[i - l].compareTo(tmpArr[j - l]) <= 0) {
                arr[k++] = tmpArr[i++ - l];
            } else {
                arr[k++] = tmpArr[j++ - l];
            }
        }
    }

}
